package com.moter.demo01.niukeoffer.数组;

/**
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
 * 来源：力扣（LeetCode）
 * 思路：贪心算法，可以赚到钱就跑路
 * 题解一，双指针：i指向买日，j指向卖日 ，i和j初始指向第一个位置
 *      如果后面一个元素小于当前元素，就把股票抛出，同时把i和j 都指向下一个位置。
 *      反之则j指向下一个元素，如果当前元素为最后一个元素，直接抛出。
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 * 题解二：贪心：
 *      每一段上升的长度相加。
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
public class Demo2 {
    public static int maxProfit(int[] prices) {
        //双指针加贪心算法。
        if(prices.length<=1) return 0;
        int res=0;
        int numi= prices[0];
        int numj=prices[0];
        for(int i =1;i<prices.length;i++){
            if(prices[i]>numj){
                numj=prices[i];
                if(i>prices.length-2)
                    res += Math.max(numj - numi, 0);
            }else {
                res += Math.max(numj - numi, 0);
                numi=prices[i];
                numj=prices[i];
            }
        }
        return res;
    }
    public int maxProfit1(int[] prices) {
        if(prices.length<=1) return 0;
        int res=0;
        for(int i =0;i<prices.length-1;i++){
            if(prices[i+1]>prices[i])
                res+=prices[i+1]-prices[i];
        }
        return res;
    }
}
